package leetcode;

import java.util.Arrays;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须原地修改，只允许使用额外常数空间。
 *
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 */
public class Code31 {
    public static void main(String[] args) {
        int[] a = new int[]{1,3,2};
        new Code31().nextPermutation(a);
        System.out.println();
    }
    public void nextPermutation(int[] nums) {
        for (int a=nums.length-1;a>0;a--){
            if(nums[a]>nums[a-1]){
                Arrays.sort(nums,a,nums.length);
                for(int b=a;b<nums.length;b++){
                    if(nums[b]>nums[a-1]){
                        int c=nums[b];
                        nums[b]=nums[a-1];
                        nums[a-1]=c;
                        break;
                    }
                }
                return;
            }
        }
        Arrays.sort(nums);
        return;
    }

    /**
     * 优化版写法
     * 考虑到后面的都是递减序列则并不需要排序进行首位替换就行了
     * @param nums
     */
    public void nextPermutation2(int[] nums) {
        if(nums == null || nums.length ==0){
            return;
        }

        int i = nums.length -2;
        while(i>=0 && nums[i] >= nums[i+1]){
            i--;
        }
        if(i >= 0){
            int j = i+1;
            while(j<nums.length && nums[j]>nums[i]){
                j++;
            }
            j--;
            swap(nums,i,j);
        }
        reverse(nums, i+1,nums.length-1);
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums,int i, int j){
        while(i < j){
            swap(nums,i++,j--);
        }
    }
}
